/**
 * LeetCode347：前K个高频元素
 * 给定一个费控的整数数组
 * 返回其中出现频率前k高的元素
 */

class MinHeap{
    constructor() {
        this.heap = [];
    }

    /**
     * @description 获取父节点的下标
     * @param {number} i
     * @return {number}
     */
    getParentIndex(i){
        // >> 是二进制操作，在二进制下向右移一位，即获取除以2得到的商
        return (i - 1) >> 1;
    }

    /**
     * @description 获取左子节点的下标
     * @param {number} i
     * @return {number}
     */
    getLeftIndex(i){
        return 2*i + 1;
    }

    /**
     * @description 获取右子节点的下标
     * @param {number} i
     * @return {number}
     */
    getRightIndex(i){
        return 2*i + 2;
    }

    /**
     * @description 交换两个位置的节点值
     * @param {number} i1
     * @param {number} i2
     */
    swap(i1,i2){
        const tmp = this.heap[i1];
        this.heap[i1] = this.heap[i2];
        this.heap[i2] = tmp;
    }

    /**
     * @description 对传入位置的节点值进行上移，直到该值小于等于其父节点值，或者上移到堆的顶部
     * @param {number} index
     */
    shiftUp(index){
        if (index == 0){ return; }
        const parentIndex = this.getParentIndex(index);
        if (this.heap[parentIndex] && this.heap[parentIndex].value > this.heap[index].value){
            this.swap(parentIndex,index);
            this.shiftUp(parentIndex);
        }
    }

    /**
     * @description 对传入位置的节点值进行下移，直到该值大于等于其子节点，或者下移到堆的底部
     * @param {number} index
     */
    shiftDown(index){
        const leftIndex = this.getLeftIndex(index);
        const rightIndex = this.getRightIndex(index);
        if (this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value){
            this.swap(leftIndex,index);
            this.shiftDown(leftIndex);
        }
        if (this.heap[rightIndex] && this.heap[rightIndex].value< this.heap[index].value){
            this.swap(rightIndex,index);
            this.shiftDown(rightIndex);
        }
    }

    /**
     * @description 在堆的底部插入一个节点，并将该节点上移到对应的位置
     * @param value
     */
    insert(value) {
        this.heap.push(value);
        this.shiftUp(this.heap.length-1);
    }

    /**
     * @description 删除堆顶元素
     */
    pop(){
        //用堆底的元素替换堆顶的元素，保持堆的结构
        this.heap[0] = this.heap.pop();
        this.shiftDown(0);
    }

    /**
     * @description 返回堆顶元素，即数组头部的元素
     * @return {*}
     */
    peek(){
        return this.heap[0];
    }

    /**
     * @description 返回堆的大小
     * @return {number}
     */
    size(){
        return this.heap.length;
    }
}

/**
 *
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums,k){
    const map= new Map();
    nums.forEach(n => {
        map.set(n, map.has(n) ? map.get(n)+1 : 1);
    });
    const h = new MinHeap();
    map.forEach((value, key) => {
        h.insert({value:key});
        if (h.size() > k){
            h.pop();
        }
    });
    return h.heap.map(a => a.key);
};

//时间复杂度：O(n * log k)
//空间复杂度：O(n)